`
https://leetcode.cn/problems/partition-equal-subset-sum/
`

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  // 复用 0-1 背包问题的思想
  // 先求出 sum ，把 nums 的每个值看成重量，判断能否刚好装满 num / 2

  const sum = nums.reduce((acc, cur) => acc + cur, 0)
  // 和为奇数时，不可能划分成两个和相等的集合
  if (sum % 2 !== 0) return false

  const n = nums.length
  const bagWeight = Math.floor(sum / 2)

  // dp[i][j] 表示前 i 个物品能否刚好装满 j 个重量
  const dp = new Array(bagWeight + 1).fill(false)

  // 背包没有空间的时候，就相当于装满了
  dp[0] = true

  for (let i = 0; i < n; i++) {
    for (let j = bagWeight; j >= 0; j--) {
      // 能装入第 i 个物品，判断是否刚好装满
      if (j - nums[i] >= 0) {
        dp[j] = dp[j] || dp[j - nums[i]]
      }
    }
  }

  return dp[bagWeight]
};